package chapter15;

import java.util.Arrays;

/**
 * 编辑距离,从x到y的最小花费
 * 操作：
 * copy: x[i]==y[j],i+1,j+1
 * replace: x[i]!=y[j],i+1,j+1
 * delete: j+1
 * insert: j+1
 * twiddle: x[i]==y[i-1]&&x[i]==x[i-1],i+2,j+2
 * kill:
 * <p>
 * 最优子结构：
 * min(cost(copy),cost(replace),cost(delete),cost(insert),cost(twiddle),cost(kill))
 * <p>
 * 思想：将x转为y需要什么操作,也就是比较不同,对于情况的不同,使用不同的操作得到相应的花费,求最小花费
 * 转矩阵
 * 例：x=aba,y=baa
 * * 0 0 a b a
 * * 0 0 0 0 0
 * * b 0 1 1 1
 * * a 0 1 2 3
 * * a 0 1 2 3
 */
public class EditDistance {

    /**
     * 编辑距离
     */
    public static int[][] editDistance(String x, String y) {
        int m = x.length();
        int n = y.length();
        int[][] c = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int cost1 = Integer.MAX_VALUE;
                int cost2 = Integer.MAX_VALUE;
                int cost3;
                int cost4 = Integer.MAX_VALUE;
                int cost5;
                int cost6 = 0;

                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    cost1 = c[i - 1][j - 1] + cost(copy);
                } else {
                    cost2 = c[i - 1][j] + cost(replace);
                }
                cost3 = c[i - 1][j] + cost(delete);
                if (i > 1 && j > 1 && i < m && j < n && x.charAt(i - 1) == y.charAt(j) && y.charAt(i) == x.charAt(j - 1)) {
                    cost4 = c[i - 2][j - 2] + cost(twiddle);
                }
                cost5 = c[i][j - 1] + cost(insert);

                if (i == m && j == n) {
                    int l = Math.max(m, n);
                    for (int k = i; k < l; k++) {
                        cost6 += cost(delete);
                    }
                    if (cost6 != 0) {
                        cost6 = Math.min(cost6, cost(kill));
                    }
                }

                c[i][j] = Math.min(cost1, Math.min(cost2, Math.min(cost3, Math.min(cost4, cost5)))) + cost6;

            }
        }

        return c;
    }

    public static void printEditDistance(String x, String y) {
        int[][] c = editDistance(x, y);
        System.out.println(Arrays.deepToString(c));
    }

    /**
     * 编辑动作的花费
     */
    public static final int copy = 0;
    public static final int replace = 1;
    public static final int delete = 2;
    public static final int insert = 3;
    public static final int twiddle = 4;
    public static final int kill = 5;

    // abc
    // cba
    public static int cost(int action) {
        if (action == copy) {
            return 1;
        }
        if (action == replace) {
            return 2;
        }
        if (action == delete) {
            return 3;
        }
        if (action == insert) {
            return 1;
        }
        if (action == twiddle) {
            return 3;
        }
        // kill
        return 4;
    }


}
